//给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 
//的整数，并以数组形式返回。 
//
// 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,3,2,7,8,2,3,1]
//输出：[2,3]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,1,2]
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 105 
// 1 <= nums[i] <= n 
// nums 中的每个元素出现 一次 或 两次 
// 
// Related Topics 数组 哈希表 
// 👍 550 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class FindAllDuplicatesInAnArray {
    public static void main(String[] args) {
        int[] nums = {4,3,2,7,8,2,3,1};
        new FindAllDuplicatesInAnArray().new Solution().findDuplicates(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 数组中数字的取值范围 [1,n][1, n][1,n]，正好与下标的范围 [0,n−1][0, n - 1][0,n−1] 对应。
         * 因此，就有一个思路，对于 nums[i]，我们将下标 = nums[i]− 1的位置的数字进行映射（还要能映射回去）。
         * 映射方法通常有两种：
         *     取反！！！
         */
        public List<Integer> findDuplicates1(int[] nums) {
            List<Integer> res = new ArrayList<>();
            // 此方法是对目标值进行修改，看看有没有被访问过，被访问过就代表重复了
            for (int num : nums) {
                if (nums[Math.abs(num) - 1] < 0) {
                    res.add(Math.abs(num));
                } else {
                    nums[Math.abs(num) - 1] *= -1;
                }
            }
            return res;
        }

        /**
         * 以增加偏移量的方法进行映射
         */
        public List<Integer> findDuplicates2(int[] nums) {
            List<Integer> res = new ArrayList<>();
            for (int num : nums) {
                if (nums[(num % 100000) - 1] > 100000) {
                    res.add(num % 100000);
                } else {
                    nums[(num % 100000) - 1] += 100000;
                }
            }
            return res;
        }


        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> res = new ArrayList<>();
            int n = nums.length;
            if (n == 0) {
                return res;
            }
            for (int i = 0; i < n; i++) {
                // 根据数值和下标进行映射，如果数字不在正确位置则进行交换，例如3放在2处
                // while循环之后保证至少能够得到一个正确位置
                while (nums[nums[i] - 1] != nums[i]){
                    swap(nums, i, nums[i] - 1);
                }
            }
            for (int i = 0; i < n; i++) // 遍历调整后的数组，不符合位置要求直接加
            {
                if (nums[i] - 1 != i) {
                    res.add(nums[i]);
                }
            }
            return res;
        }

        private void swap(int[] nums, int i, int j) {
            if (i == j) {
                return;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}